The present invention relates to resource reservations within a distributed network. It finds particular application in conjunction with setting-up and maintaining reservations within the Internet, and will be described with particular reference thereto. It will be appreciated, however, that the invention is also amenable to other like applications.
A resource reservation enables guaranteed communication between end-to-end resources (e.g., a source and a destination). Such guaranteed communication is critical for time-sensitive applications including Internet telephony, multimedia-on-demand, and interactive computer games.
The deployment of inter-domain resource reservations in the Internet has been delayed by the desire of each carrier to control its own routing and resource management policies. Carriers appear to prefer having relatively narrow interfaces to the rest of the Internet. One drawback to such narrow interfaces is that they only present a limited amount of network connectivity and resource sharing information at a network""s borders.
The size of the Internet has grown rapidly over the past several years. This growth is expected to continue into the future. As the Internet grows, the processes involved with creating and maintaining resource reservations across the network become more complicated. The increased complexity tends to slow down the formation of resource reservations and requires more network resources for maintaining the reservations once they are created. Therefore, it is desirable to scale resource reservation protocols with the size of the Internet.
Inter-domain resource reservations must satisfy a number of criteria in order to scale with the expanding Internet. More specifically, resource reservations must reduce the storage of reservation information, reduce the cost of processing reservation messages, reduce the bandwidth consumed by reservation information, and simplify the delivery commitments to peering domains.
Routers store reservation control information tables and packet classifier tables. The size of these tables is typically a function of the number of end users n. In conventional systems, the reservation control information tables and packet classifier tables include n2 entries. Considering the growth of the Internet, such table sizes are becoming unmanageable.
The cost of processing reservation messages depends on the complexity of handling each message and the frequency of reservation messages. Conventional end-applications set-up reservations across domains. Therefore, reservation updates are relatively frequent. Along with increasing Internet traffic, frequent reservation updates also increase the cost of processing reservation messages.
Ideally, bandwidth consumed by reservation information exchange is small relative to the link bandwidth, both in steady state and with routing transients. This bandwidth overhead is typically proportional to the number of states kept in routers. Because the number of states kept in the routers is n2 (where n is the number of users), bandwidth overhead is becoming a significant factor as the Internet continues to grow.
It is desirable that each domain manage its own network resources and enforce its own internal traffic engineering policies. This implies that a domain only reveals simple delivery commitments to its peering domains. The inter-domain reservation then uses these delivery commitments to establish a reservation path through multiple domains. Each domain sets-up transit reservation flows using its preferred intra-domain reservation mechanism. As the Internet grows, a need exists for connecting multiple reservation segments from various domains together in a more efficient manner.
Both router-based and server-based systems have presented scalable resource reservations. However, as discussed below, these systems include various drawbacks.
Current router-based approaches are available that modify the conventionally used reservation protocol (xe2x80x9cRSVPxe2x80x9d) to support scalable reservations. These router-based approaches allow routers to aggregate individual reservation requests. However, they do not address state storage scaling issues (e.g., aggregated reservations are received in RSVP Sender Template and Session pairs). Furthermore, these conventional router-based approaches set-up reservations between every pair of domains that communicate via reserved flows. Therefore, the storage states scale as a function of the square of the communicating domains. Given that there are currently more than 4,500 domains, such a condition is undesirable.
In current server-based approaches, a bandwidth broker (or agent) in each domain is responsible for selecting and setting-up aggregated reservation sessions. This approach has the advantage of removing message processing and storage burdens from the routers. However, synchronizing reservation information among the bandwidth brokers and the border routers is a complex process. Furthermore, the processing overhead remains (and is simply moved to a different network entity). Also, there is a potential that a new single point of failure for the entire domain is introduced.
Two-tier reservation models have also been proposed. In these models, intra-domain reservation protocols are used within a domain to set-up reserved flows between senders and receivers. Inter-domain reservation protocols set-up coarsely-measured reserved flows between domains. Although two-tier models have been proposed, the actual mechanisms for implementing these models have not been defined.
The present invention provides a new and improved apparatus and method which overcomes the above-referenced problems and others.
A method creates a reserved communication tree for state aggregation. A stateless probe, which requests a specified bandwidth, is sent from a leaf router toward a root router within a network. The stateless probe discovers a communication path, potentially including intermediate routers, between the leaf router and the root router. A graft message is returned from the root router to the leaf router along the communication path. A bandwidth reservation is created within each of the routers through which the graft message travels. Each of the bandwidth reservations is as large as the specified amount and is associated with an adjacent router in the communication path. A reserved communication path is established within the network. The reserved communication path includes the root router, any of the intermediate routers, the leaf router, and a bandwidth reservation for each of the routers along the reserved communication path. The established communication path is aggregated with other established communication paths to form a reserved communication tree.
One advantage of the present invention is that it aggregates individual reservation requests.
Another advantage of the present invention is that it scales, in terms of state storage, processing, and bandwidth, as a function of the number of communicating domains.
Still further advantages of the present invention will become apparent to those of ordinary skill in the art upon reading and understanding the following detailed description of the preferred embodiments.